The invention relates in general to decoders and in particular to a decoder for executing a Viterbi algorithm.
A Viterbi algorithm makes it possible to correct transmission errors in communications systems. The application of a Viterbi algorithm is also known from many other search problems, for example in the field of pattern recognition. The Viterbi algorithm has a disadvantage that the computation is very complex, thereby requiring a relatively large amount of memory resources. As a consequence, a system clock frequency of a decoder for executing a Viterbi algorithm is typically correspondingly high. The system clock frequency at which the individual operations of the Viterbi algorithm are to be executed is generally several times higher than the data rate when the algorithm is employed in communications systems. This requirement is of note particularly in systems having very high data rates, such as digital video broadcasting (“DVB”) systems, because the requisite clock frequencies necessitate the use of relatively expensive technology.
The principle of a Viterbi decoder is known, for example, from G. David Forney, Jr., “The Viterbi Algorithm,” Proc. IEEE, Vol. 61, No. 3, March 1973, pp. 268-278. Modules used in such a decoder for calculating distances or total distances and for calculating accumulations and comparisons, as well as a generic structure of a logical module for a Viterbi decoder, are employed in decoders according to European Published Patent Application EP 0 769 853 A1. Possibilities for parallelization are known from H. Burckhardt and L. C. Barbosa, “Contributions to the Application of the Viterbi Algorithm,” IEEE Trans. on IT, Vol. 31, No. 5, September 1985, pp. 626-634.
Prior art Viterbi decoders and Viterbi algorithms typically require a relatively high system clock frequency.
One embodiment of a prior art Viterbi decoder 10 having a degree of parallelization p is illustrated in FIG. 8. Via a receiver bus 12, K×N bits of received data r(n, k) are provided to a total-distance module 14. In the module 14, total distances are calculated and correspondingly 2K×(N+1d(K)) bits are provided on a bus 16 to a computing device 18 having accumulate-and-compare modules 20. The total distances are stored in a temporary memory 22. Via a bidirectional distance bus 24, 2×(N+1d(K)+1)×2p+1 bits are correspondingly transmitted from the computing device 18 to a distance memory 26 that stores (N+1d(K)+1)×2L−1 bits. Here L is the length of generator polynomials, of which a set containing a number K is to be considered in the calculation. The received data r(n, k) on the bus 12 are resolved to N bits. The degree of parallelization is p. From the distance memory 26, a corresponding number of 2×(N+1d(K)+1)×2p+1 bits are transmitted on the distance bus 24 back to the computing device 18.
The computing device 18 is also connected to a path memory 28 via a bidirectional path bus 30 where 2×T×2p+1 bits are transmitted from the path memory 28 or a second temporary memory 32 of the computing device 18 to and from the path memory 28 via the path bus 30. In the path memory 28, T×2L−1 bits are stored. After corresponding calculations, in particular accumulations and comparisons, have been executed in the accumulate-and-compare modules 20, a search is executed in the computing device 18 and a data bit string c(n, k) determined to be the most desirable is furnished on a line 34 at the output of the Viterbi decoder 10.
In such a Viterbi decoder 10, a lower system clock frequency can be attained with a plurality of parallel modules, depending on the degree of parallelization (0<p<L−2). In the case where the system clock frequency is equal to the data rate (p=L−2), all 2L−1 accumulate-and-compare modules 20 are implemented in parallel. The bus then becomes the limiting factor. For available embodiments, it may be that no acceptable compromise can be found between the system clock frequency and the requisite bus widths of the path bus 30 and the distance bus 24.
FIG. 9 illustrates the ratio between the system clock frequency and bus width as functions of the degree of parallelization p for the case of such a Viterbi decoder for DVB systems. Typical parameters are L=7, K=2 and T=64 for data rates up to 50 Mbit/s. If there is no parallelization (p=0) and the bus width is relatively small, a system clock frequency of 1600 MHz is used. If the system clock frequency is to be equal to the data rate (i.e., the degree of parallelization is p=5) a bandwidth of 9000 bits is needed for the bus width. In practice this is not acceptable in light of the realization and the costs arising therefrom. Given an acceptable system clock frequency of up to 100 MHz (p=4), the requisite bus width of 4500 bits is still relatively high for a commercially favorable approach.
What is needed is a Viterbi decoder for executing a Viterbi algorithm that allows the system clock frequency to equal the data rate at relatively high bit rates.